// #include<iostream>
// #include<vector>
#include <bits/stdc++.h>
using namespace std;

// O(n^2)，最好O(n)，空间O(1)，原地排序，稳定
void BubbleSort(vector<int>& nums) {
    for (int i = 1; i < nums.size(); ++i) {
        bool flag = false;
        for (int j = 0; j < nums.size() - i; ++j) {
            if (nums[j] > nums[j + 1]) {
                swap(nums[j], nums[j + 1]);
                flag = true;
            }
        }
        if (!flag) break;
    }
}

// O(n^2)，最好O(n)，空间O(1)，原地排序，稳定
void InsertSort(vector<int>& nums) {
    for (int i = 1; i < nums.size(); ++i) {
        int tmp = nums[i];
        int j = i - 1;
        for (; j >= 0; --j) {
            if (tmp < nums[j]) {
                nums[j + 1] = nums[j];
            }
            else break;
        }
        nums[j + 1] = tmp;
    }
}

// O(n^2)，最好O(n^2)，空间O(1)，原地排序，不稳定
void SelectSort(vector<int>& nums) {
    for (int i = 0; i < nums.size(); ++i) {
        int minIdx = i;
        for (int j = i; j < nums.size(); ++j) {
            if (nums[j] < nums[minIdx]) minIdx = j;
        }
        if (minIdx != i)
            swap(nums[i], nums[minIdx]);
    }
}

// O(nlogn)，最差O(n^2)，空间O(logn)，原地，不稳定
int getMid(vector<int>& nums, int st, int nd);
void QuickSort(vector<int>& nums, int st, int nd) {
    if (st >= nd) return;
    int mid = getMid(nums, st, nd);
    QuickSort(nums, st, mid - 1);
    QuickSort(nums, mid + 1, nd);
}

int getMid(vector<int>& nums, int st, int nd) {
    int pivot = nums[st];
    int left = st, right = nd;
    while (left < right) {
        while (left < right && nums[right] >= pivot) --right;
        nums[left++] = nums[right];
        while (left < right && nums[left] <= pivot) ++left;
        nums[right--] = nums[left];
    }
    nums[left] = pivot;
    // cout<<left<<endl;
    return left;
}

// O(nlogn)，空间O(n)，非原地，稳定
void merge(vector<int>&, int, int, int);
void MergeSort(vector<int>& nums, int st, int nd) {
    if (st < nd) {
        int mid = st + (nd - st) / 2;
        MergeSort(nums, st, mid);
        MergeSort(nums, mid + 1, nd);
        merge(nums, st, mid, nd);
    }

}

void merge(vector<int>& nums, int st, int mid, int nd) {
    vector<int> mergeVec;
    int begin1 = st, begin2 = mid + 1;
    while (begin1 <= mid && begin2 <= nd) {
        if (nums[begin1] <= nums[begin2]) mergeVec.push_back(nums[begin1++]);
        else mergeVec.push_back(nums[begin2++]);
    }
    while (begin1 <= mid) mergeVec.push_back(nums[begin1++]);
    while (begin2 <= nd) mergeVec.push_back(nums[begin2++]);
    for (int i = 0; i < mergeVec.size(); ++i) nums[st+i] = mergeVec[i];
}

//O(n + k)，非原地排序，空间O(n + k)，稳定
void CountSort(vector<int>& nums) {
    int minVal = *min_element(nums.begin(), nums.end());
    int maxVal = *max_element(nums.begin(), nums.end());
    vector<int> count(maxVal - minVal + 1, 0);
    for (int i = 0; i < nums.size(); ++i) {
        ++count[nums[i] - minVal];
    } 
    for (int i = 1; i < count.size(); ++i) count[i] += count[i - 1];
    for (int n: count) cout<<n<<' ';
    cout<<endl;
    vector<int> newNums(nums.size());
    for (int i = nums.size() - 1; i >= 0; --i) {
        newNums[--count[nums[i] - minVal]] = nums[i];
    }
    for (int i = 0; i < nums.size(); ++i) nums[i] = newNums[i];
}
//O(nlogn), 空间O(1)，原地排序，不稳定
//把以下代码反过来，用大顶堆，就可以实现原地排序
void heapfy(vector<int>&, int, int);
void HeapSort(vector<int>& nums) {
    for (int i = 0; i < nums.size() / 2; ++i) heapfy(nums, i, nums.size());
    cout<<endl;
    vector<int> newNums;
    int n = nums.size();
    while (n--) {
        newNums.push_back(nums[0]);
        swap(nums[0], nums[n]);
        heapfy(nums, 0, n);
    }
    for (int i = 0; i < nums.size(); ++i) nums[i] = newNums[i]; 
}

void heapfy(vector<int>& nums, int i, int n) {
    while (1) {
        int minIdx = i;
        if (2*i+1 < n && nums[2*i+1] < nums[minIdx]) minIdx = 2*i+1;
        if (2*i+2 < n && nums[2*i+2] < nums[minIdx]) minIdx = 2*i+2;
        if (minIdx == i) break;
        swap(nums[i], nums[minIdx]);
        i = minIdx;
    }
}

// 最坏/平均O(n(logn)^2)，最好O(n), 空间O(1)，原地排序，不稳定（？）
void ShellSort(vector<int>& nums) {
    int interval = nums.size() / 2;
    while (interval >= 1) {
        for (int i = interval; i < nums.size(); ++i) {
            int tmp = nums[i];
            int j = i;
            for (; j >= 0; j -= interval) {
                if (j - interval >= 0 && nums[j - interval] > tmp) nums[j] = nums[j - interval];
                else break;
            }
            nums[j] = tmp;
        }
        interval /= 2;
    }
}

// O(n*k) 空间O(n + k)，非原地 稳定 
void RadixSort(vector<int>& nums) {
    int digit = 1;
    while (1) {
        bool flag = false;
        vector<int> digitNums(nums.size());
        vector<int> count(10, 0);
        for (int i = 0; i < nums.size(); ++i) {
            // digitNums[i] = nums[i] / digit % 10;
            // if (digitNums[i] != 0) flag = true;
            int n = nums[i] / digit % 10;
            if (n != 0) flag = true;
            digitNums[i] = n;
            ++count[n];
        }
        if (!flag) break;
        for (int i = 1; i < 10; ++i) count[i] += count[i - 1];
        vector<int> newNums(nums.size());
        for (int i = nums.size() - 1; i >= 0; --i) 
            newNums[--count[digitNums[i]]] = nums[i];
        for (int i = 0; i < nums.size(); ++i) nums[i] = newNums[i];
        digit *= 10;
    }
}
//O(n*(?)) 原地？稳定？
// void BucketSort(vector<int> nums) {

// }
int main() {
    vector<int> nums{32,53,12,19,7,7};
    // BubbleSort(nums);
    // InsertSort(nums);
    // SelectSort(nums);
    // QuickSort(nums, 0, nums.size() - 1);
    // MergeSort(nums, 0, nums.size() - 1);
    // CountSort(nums);
    // HeapSort(nums);
    // ShellSort(nums);
    RadixSort(nums);
    for (int n: nums) cout<<n<<' ';
    cout<<endl;
    return 0;
}